import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;


import java.util.LinkedList;
import java.util.List;


/**
 * 279.完全平方数
 * 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
 * <p>
 * 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
 */
public class NumSquares {

    @Test
    public void test1() {
        Assertions.assertEquals(3, numSquares(12));
    }

    @Test
    public void test2() {
        Assertions.assertEquals(2, numSquares(13));
    }

    @Test
    public void test3() {
        Assertions.assertEquals(1, numSquares(1));
    }

    @Test
    public void test4() {
        Assertions.assertEquals(2, numSquares(293));
    }

    @BeforeEach
    public void init() {

        result = Integer.MAX_VALUE;
        list = new LinkedList<>();
    }


    List<Integer> list;

    int result;


    int numSquares(int n) {


        for (int i = 1, square = 1; i * i <= n; i++) {

            square = i * i;

            list.add(square);
        }
        find(list.size() - 1, n, 0);
        return result;
    }

    private void find(int index, int target, int count) {

        if (count > result) {
//            性能优化的关键在这里
//            如果此次要找的结果的已经大于当前的结果了，那就没必要继续往下找了
            return;
        } else if (target == 0) {
//          因为这里是第二个if判断，第一个if已经保证了 count一定是小于 result的
//          所以这里不用 Math.min 再来判断一次了
            result = count;
        } else if (target < 0) {
            return;
        }


        for (int i = index; i >= 0; i--) {
            /*
             * 从后往前找（先找大数，再找小数），这样效率高
             * 从每次优先选择最大数的角度上来看的话，算是贪心算法
             * */
            Integer val = list.get(i);

            find(i, target - val, count + 1);

        }

    }
}
